Palindrome permutation II

Time: O(NxN!); Space: O(N); medium

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example 1:

Input: s = “aabb”

Output: [“abba”,“baab”]

Example 2:

Input: “abc”

Output: []

[4]:

import collections

class Solution1(object):
    """
    Time: O(N*N!)
    Space: O(N)
    """
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        cnt = collections.Counter(s)
        mid = ''.join(k for k, v in cnt.items() if v % 2)
        chars = ''.join(k * (v // 2) for k, v in cnt.items())
        return self.permuteUnique(mid, chars) if len(mid) < 2 else []

    def permuteUnique(self, mid, nums):
        result = []
        used = [False] * len(nums)
        self.permuteUniqueRecu(mid, result, used, [], nums)
        return result

    def permuteUniqueRecu(self, mid, result, used, cur, nums):
        if len(cur) == len(nums):
            half_palindrome = ''.join(cur)
            result.append(half_palindrome + mid + half_palindrome[::-1])
            return

        for i in range(len(nums)):
            if not used[i] and not (i > 0 and nums[i-1] == nums[i] and used[i-1]):
                used[i] = True
                cur.append(nums[i])
                self.permuteUniqueRecu(mid, result, used, cur, nums)
                cur.pop()
                used[i] = False

[5]:

sol = Solution1()
s = "aabb"
assert sol.generatePalindromes(s) == ["abba","baab"]
s = "abc"
assert sol.generatePalindromes(s) == []

[11]:

import collections
import itertools

class Solution2(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        cnt = collections.Counter(s)
        mid = tuple(k for k, v in cnt.items() if v % 2)
        chars = ''.join(k * (v // 2) for k, v in cnt.items())

        return [''.join(half_palindrome + mid + half_palindrome[::-1]) \
                 for half_palindrome in set(itertools.permutations(chars))] if len(mid) < 2 else []

[13]:

sol = Solution2()
s = "aabb"
assert sol.generatePalindromes(s) == ["abba","baab"] or ["baab","abba"]
s = "abc"
assert sol.generatePalindromes(s) == []